package shapes.shapes2D.polygon 
{
	import flash.geom.Point;
	/**
	 * ...
	 * @author Nicolas Barradeau
	 * http://en.nicoptere.net
	 */
	public class Intersection
	{
		static private var ip:Point = new Point();
		
		public function Intersection() 
		{
			
		}
		
		
		//---------------------------------------------------------------
		//Checks for intersection of Segment if as_seg is true.
		//Checks for intersection of Line if as_seg is false.
		//Return intersection of Segment AB and Segment EF as a Point
		//Return null if there is no intersection
		//---------------------------------------------------------------
		static public function lineIntersectLine (	A : Point, B : Point,
													E : Point, F : Point,
													ABasSeg : Boolean = true, EFasSeg : Boolean = true ) : Point
		{
			
			var a1:Number;
			var a2:Number;
			var b1:Number;
			var b2:Number;
			var c1:Number;
			var c2:Number;
		 
			a1= B.y-A.y;
			b1= A.x-B.x;
			c1= B.x*A.y - A.x*B.y;
			a2= F.y-E.y;
			b2= E.x-F.x;
			c2= F.x*E.y - E.x*F.y;
		 
			var denom:Number=a1*b2 - a2*b1;
			if (denom == 0) {
				return null;
			}
			ip=new Point();
			ip.x=(b1*c2 - b2*c1)/denom;
			ip.y=(a2*c1 - a1*c2)/denom;
		 
			//---------------------------------------------------
			//Do checks to see if intersection to endpoints
			//distance is longer than actual Segments.
			//Return null if it is with any.
			//---------------------------------------------------
			if ( A.x == B.x )
				ip.x = A.x;
			else if ( E.x == F.x )
				ip.x = E.x;
			if ( A.y == B.y )
				ip.y = A.y;
			else if ( E.y == F.y )
				ip.y = E.y;

			//	Constrain to segment.

			if ( ABasSeg )
			{
				if ( ( A.x < B.x ) ? ip.x < A.x || ip.x > B.x : ip.x > A.x || ip.x < B.x )
					return null;
				if ( ( A.y < B.y ) ? ip.y < A.y || ip.y > B.y : ip.y > A.y || ip.y < B.y )
					return null;
			}
			if ( EFasSeg )
			{
				if ( ( E.x < F.x ) ? ip.x < E.x || ip.x > F.x : ip.x > E.x || ip.x < F.x )
					return null;
				if ( ( E.y < F.y ) ? ip.y < E.y || ip.y > F.y : ip.y > E.y || ip.y < F.y )
					return null;
			}
			return ip;
		}
		
		/*---------------------------------------------------------------------------
		Returns an Object with the following properties:
			enter			-Intersection Point entering the circle.
			exit			-Intersection Point exiting the circle.
			inside			-Boolean indicating if the points of the line are inside the circle.
			tangent		-Boolean indicating if line intersect at one point of the circle.
			intersects		-Boolean indicating if there is an intersection of the points and the circle.
		 
		If both "enter" and "exit" are null, or "intersects" == false, it indicates there is no intersection.
		 
		This is a customization of the intersectCircleLine Javascript function found here:
		 
		http://www.kevlindev.com/gui/index.htm
		 
		----------------------------------------------------------------------------*/
		static public function lineIntersectCircle(A : Point, B : Point, C : Point, r : Number = 1):Object
		{
			var result : Object = new Object ();
			result.inside = false;
			result.tangent = false;
			result.intersects = false;
			result.enter=null;
			result.exit = null;
			
			var a : Number = (B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y);
			var b : Number = 2 * ((B.x - A.x) * (A.x - C.x) +(B.y - A.y) * (A.y - C.y));
			var cc : Number = C.x * C.x + C.y * C.y + A.x * A.x + A.y * A.y - 2 * (C.x * A.x + C.y * A.y) - r * r;
			var deter : Number = b * b - 4 * a * cc;
			if (deter <= 0 ) {
				result.inside = false;
			} else {
				var e : Number = Math.sqrt (deter);
				var u1 : Number = ( - b + e ) / (2 * a );
				var u2 : Number = ( - b - e ) / (2 * a );
				if ((u1 < 0 || u1 > 1) && (u2 < 0 || u2 > 1)) {
					if ((u1 < 0 && u2 < 0) || (u1 > 1 && u2 > 1)) {
						result.inside = false;
					} else {
						result.inside = true;
					}
				} else {
					if (0 <= u2 && u2 <= 1) {
						result.enter=Point.interpolate (A, B, 1 - u2);
					}
					if (0 <= u1 && u1 <= 1) {
						result.exit=Point.interpolate (A, B, 1 - u1);
					}
					result.intersects = true;
					if (result.exit != null && result.enter != null && result.exit.equals (result.enter)) {
						result.tangent = true;
					}
				}
			}
			return result;
		}
		
		
		/*---------------------------------------------------------------------------
		Returns an Object with the following properties:
		intersects        -Boolean indicating if an intersection exists.
		start_inside      -Boolean indicating if Point A is inside of the polygon.
		end_inside       -Boolean indicating if Point B is inside of the polygon.
		intersections    -Array of intersection Points along the polygon.
		centroid          -A Point indicating "center of mass" of the polygon.
		 
		"pa" is an Array of Points.
		----------------------------------------------------------------------------*/
		static public function lineIntersectPoly(A : Point, B : Point, pa:Array):Object 
		{
			var An:int=1;
			var Bn:int=1;
			var C:Point;
			var D:Point;
			var i:Point;
			var cx:Number=0;
			var cy:Number=0;
			var result:Object = new Object();
			pa.push(pa[0]);
			result.intersects = false;
			result.intersections=[];
			result.start_inside=false;
			result.end_inside=false;
			var n:int=pa.length-1;
			while(n > -1){
				C=Point(pa[n]);
				if (n > 0)
				{
					cx+=C.x;
					cy+=C.y;
					
					D = Point(pa[n - 1]) || Point(pa[0]);
					i = lineIntersectLine(A, B, C, D);
					if(i != null){
						result.intersections.push(i);
					}
					if(lineIntersectLine(A,new Point(C.x+D.x,A.y),C,D) != null){
						An++;
					}
					if(lineIntersectLine(B,new Point(C.x+D.x,B.y),C,D) != null){
						Bn++;
					}
				}
				n--;
			}
			if(An % 2 == 0){
				result.start_inside=true;
			}
			if(Bn % 2 == 0){
				result.end_inside=true;
			}
			result.centroid = new Point(cx / (pa.length - 1), cy / (pa.length - 1));
			result.intersects = result.intersections.length > 0;
			return result;
		}
		
		
		/*---------------------------------------------------------------------------
		Returns Array of intersection Points on a quadratic curve.
		An empty Array is returned if no intersection is found.
		 
		Parameters:
		A		-Start Point of a segment to make intersection.
		B		-End Point of a segment to make intersection.
		sp		-Start Point of curve.
		cp		-Control Point of curve.
		ep		-End Point of curve.
		rez		-The resolution of curve tests
		Note: Uses another function for testing the intersections:
		 
		http://keith-hair.net/blog/2008/08/04/find-intersection-point-of-two-lines-in-as3/
		 
		----------------------------------------------------------------------------*/
		static public function lineToQCurve_Intersect(A:Point,B:Point,sp:Point,cp:Point,ep:Point,rez:Number=80):Array
		{
			//rez less than 2 is almost "Pointless" LOL.
			var low:Number=2;
			var high:Number=99; //100 causes infinite loop.
			rez=Math.min(Math.max(Math.min(low,high),rez),high);
			var t:Number=0;
			var ft:Number=0;
			var n:Number=99/rez;
			var C:Point=new Point();
			var D:Point=new Point();
			var L:Point=new Point();
			var ip:Point;
			var a:Array=[];
			//test possible segment intersections in a loop.
			var z:int=100;
			while (z > -1)
			{
				t=z/100;
				C.x=Math.pow(1-t,2)*sp.x+2*(1-t)*t*cp.x+Math.pow(t,2)*ep.x;
				C.y=Math.pow(1-t,2)*sp.y+2*(1-t)*t*cp.y+Math.pow(t,2)*ep.y;
				D=L;//Connect start to last end point
				L=C.clone();
				if (z == 100) {
					D=ep.clone();
				}
				ip=lineIntersectLine(A,B,C,D);
				if (ip != null) {
					a.push(ip);
					if(a.length == 2){
						break;
					}
				}
				z-=n;
			}
			return a;
		}
		
		/*---------------------------------------------------------------------------
		Returns the closest Point on Line "AB" to Point "p":
		 
		p			-Point, the Point to constrain to the line.
		A			-Point, beginning Point of Line.
		B			-Point, ending Point of Line.
		as_seg	-Boolean, limits return Point between endpoints of A and B.
		----------------------------------------------------------------------------*/
		static public function constrainPointToLine(p:Point,A:Point,B:Point,as_seg:Boolean=false):Point
		{
			var cp:Point=new Point();
			var dx:Number;
			var dy:Number;
			var t:Number;
		 
			dx = B.x - A.x;
			dy = B.y - A.y;
			if (dx == 0 && dy == 0) {
				cp.x = A.x;
				cp.y = A.y;
			}else{
				t = ((p.x - A.x) * dx + (p.y - A.y) * dy) / (dx * dx + dy * dy);
				if (as_seg){
					t = Math.min(Math.max(0,t),1);
				}
				cp.x = A.x + t * dx;
				cp.y = A.y + t * dy;
			}
			return cp;
		}
		
	}

}